package lc.q151_200;

import lc.ListNode;

import java.util.ArrayList;
import java.util.HashSet;
import java.util.List;
import java.util.Set;

public class Q160 {

    public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
        ListNode firstA = headA;
        ListNode firstB = headB;
        // 如何进一？
        // 方式一，双重遍历
//        while (firstA != null) {
//            while (firstB != null && firstA != firstB) {
//                firstB = firstB.next;
//            }
//            if (firstA == firstB) {
//                return firstA;
//            }
//            firstA = firstA.next;
//            firstB = headB;
//
//        }
        // 方式二，从后往前走，即构造列表倒序排序
//        List<ListNode> aList = new ArrayList<>();
//        List<ListNode> bList = new ArrayList<>();
//        while (firstA != null) {
//            aList.add(firstA);
//            firstA = firstA.next;
//        }
//        while (firstB != null) {
//            bList.add(firstB);
//            firstB = firstB.next;
//        }
//        // 倒序排序ablist
//        int i = aList.size() - 1;
//        int j = bList.size() - 1;
//        while (i >= 0 && j >= 0) {
//            if (aList.get(i) == bList.get(j)) {
//                // 则ij相减
//                i --;
//                j --;
//            } else {
//                break;
//            }
//        }
//        if (i < aList.size() - 1 && j < bList.size() - 1) {
//            return aList.get(i + 1);
//        }
        // 方式三，直接hash
//        Set<ListNode> c = new HashSet<ListNode>();
//        while (firstA != null) {
//            c.add(firstA);
//            firstA = firstA.next;
//        }
//        while (firstB != null) {
//            if (c.contains(firstB)) {
//                return firstB;
//            }
//            firstB = firstB.next;
//        }
        // 方式四，双指针，两个指针同时遍历A和B，一个先A后B，一个先B后A
        while (firstA != firstB) {
            firstA = firstA == null ? headB : firstA.next;
            firstB = firstB == null ? headA : firstB.next;
        }
        return firstA;

    }
}
